// 题目：
// 一群孩子站成一排，每一个孩子有自己的评分。现在需要给这些孩子发糖果，规则是如果一
// 个孩子的评分比自己身旁的一个孩子要高，那么这个孩子就必须得到比身旁孩子更多的糖果；所
// 有孩子至少要有一个糖果。求解最少需要多少个糖果。
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
#include <numeric>

// 一群学生的评分
std::vector<int> students = {1,2,3,4,5};
// <students下标， 该学生获得的对应糖果数>
std::map<int, int> candies;

/************************我自己的写法******************************
整体思路：
使用递归的做法，每次都是先找到还没拿到糖果的孩子里，评分最低
的那个，然后判断这个孩子左边两边是不是已经给过糖果了。如果对方还没有糖果，
则对你没约束；如果已经有糖果了，判断你的评分是不是比对方高，是的话你的糖
果就必须比对方多，否则还是对你没约束。
******************************************************************/
// fisrt 与 last 均是指向students某个位置的迭代器，组成一个左闭右开区间
void SetCandy(std::vector<int>::iterator first,
              std::vector<int>::iterator last) {
  // 先找当前区间的最小位置
  auto min_iter = std::min_element(first, last);

  // 相等表示没找到，通常表明区间为空
  if (min_iter != last) {
    // 当前找到的最小评分在students这个全集里的下标
    auto pos = min_iter - students.begin();

    // 判断左右的孩子对当前的孩子是否有约束（已经给过糖果，且评分比当前孩子低）
    // 如果左边或者右边没有孩子，也算那边没约束。
    bool left = false;
    bool right = false;
    if (min_iter > students.begin()) {
      left = (candies.count(pos - 1) > 0) && (students[pos] > students[pos - 1]);
    }

    if (min_iter < students.end() - 1) {
      right = (candies.count(pos + 1) > 0) && (students[pos] > students[pos + 1]);
    }

    if (left && right) {
      // 左右都有约束，取糖果多的那个+1
      candies[pos] = std::max(candies[pos - 1], candies[pos + 1]) + 1;
    } else if (left) {
      // 只有左边有约束，取左边的糖果+1
      candies[pos] = candies[pos - 1] + 1;      
    } else if (right) {
       // 只有右边有约束，取右边的糖果+1
       candies[pos] = candies[pos + 1] + 1;     
    } else {
      // 两边都没有约束，给最少得糖果，1个
      candies[pos] = 1;
    }

    // 递归，以找到的评分最低的孩子为中点，分成左右两个区域
    // 在左右两个区域用同样的逻辑再次找评分最低的孩子，给糖果
    SetCandy(first, min_iter);
    SetCandy(min_iter + 1, last);
  } else {
    return;
  }
}

// 书里的解法
int candy(std::vector<int>& ratings) {
  int size = ratings.size();
  if (size < 2) {
    return size;
  }
  std::vector<int> num(size, 1);
  for (int i = 1; i < size; ++i) {
    if (ratings[i] > ratings[i - 1]) {
      num[i] = num[i - 1] + 1;
    }
  }
  for (int i = size - 1; i > 0; --i) {
    if (ratings[i] < ratings[i - 1]) {
      num[i - 1] = std::max(num[i - 1], num[i] + 1);
    }
  }
  return std::accumulate(num.begin(), num.end(), 0);  // std::accumulate 可以很方便地求和
}

int main() {
  SetCandy(students.begin(), students.end());

  // 将每个孩子的糖果数相加
  int total_candy = 0;
  for (const auto& candy : candies) {
    total_candy += candy.second;
  }  

  std::cout << total_candy << " " << candy(students) << std::endl;
  return 0;
}